#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:
    //滑动窗口
    int maxSubArray(vector<int>& nums) {
        int l=0;
        int cur=nums[l],m=cur;
        for(int r=1;r<nums.size();r++){
            if(nums[r]>=0&&cur<0||nums[r]<0&&cur<0&&nums[r]>cur)
                cur=nums[r],l=r;
            else
                cur+=nums[r];
            m=max(m,cur);
        }
        return m;
    }
    //动态规划
        int maxSubArray(vector<int>& nums) {
        //状态表示 dp[i] [0,i]位置最大连续子数组和 x
        //              以i位置为结尾的所有子数组的最大和
        //状态转移方程: dp[i]=max(nums[i],dp[i-1]+nums[i]);
        //初始化 dp[0]=nums[i];
        //返回值 max_element(dp.begin(),dp.end());
        for(int i=1;i<nums.size();i++){
            nums[i]=max(nums[i-1]+nums[i],nums[i]);
        }
        return *max_element(nums.begin(),nums.end());
    }
};